# -*- coding: utf-8 -*-
# @Time  : 2021/8/2 下午10:54
# @Author : huangyuan
# @Project : algorithm
# @FileName: SingleLinkedList.py
# @Description: 链表类


# 节点类
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


# 单向链表
class SingleLinkedList:
    def __init__(self):
        # 头指针
        self.head = Node(None)
        # 尾指针
        self.trail = self.head
        # 链表容量
        self.size = 0

    # 迭代
    def __iter__(self):
        return SingleLinkedListIter(self.head)

    # 插入元素 - 在链表末尾插入数据
    def insert(self, item):
        new = Node(item)
        self.trail.next = new
        self.trail = new
        self.size += 1

    # 移除元素 - 移除链表末尾的数据
    def remove(self):
        if self.is_empty():
            raise RuntimeError("链表为空，无法删除")
        # 获取链表末尾第二个节点
        front = self.penultimate_node(self.head)
        front.next = None
        self.trail = front
        self.size -= 1

    # 寻找链表末尾第二个节点 - 如果链表只有一个节点则获取的该节点就为链表头节点
    def penultimate_node(self, head):
        if self.is_empty():
            return None
        front = head
        # 如果节点next为空，说明已经到链表末尾
        while head.next is not None:
            front = head
            head = head.next
        return front

    # 判断链表是否为空
    def is_empty(self):
        return self.size == 0

    # 删除指定值节点
    def remove_item(self, item):
        if self.is_empty():
            raise RuntimeError("链表为空，无法删除")
        # 获取链表头节点
        point = self.head
        while point.next is not None:
            if point.next.item == item:
                if point.next.next is not None:
                    point.next = point.next.next
                else:
                    # 删除最后一个节点时，尾指针要指向上个节点
                    point.next = None
                    self.trail = point
                self.size -= 1
                return
            point = point.next


# 链表迭代器对象
class SingleLinkedListIter:
    # 构造器
    def __init__(self, head):
        self.head = head

    # 可迭代对象要实现的方法，返回迭代器
    def __iter__(self):
        return self

    # 迭代器要实现的方法，返回下一个元素值
    def __next__(self):
        if self.head.next is None:
            raise StopIteration
        else:
            item = self.head.next.item
            self.head = self.head.next
            return item


if __name__ == '__main__':
    linked_list = SingleLinkedList()
    linked_list.insert(1)
    linked_list.insert(2)
    linked_list.insert(3)
    linked_list.insert(4)
    linked_list.insert(5)
    print(f"链表长度为: {linked_list.size}")
    for value in linked_list:
        print(value)
    print("-------------------")
    linked_list.remove_item(2)
    linked_list.remove_item(5)
    print(f"链表长度为: {linked_list.size}")
    for value in linked_list:
        print(value)
    print("-------------------")
    linked_list.insert(7)
    linked_list.insert(8)
    print(f"链表长度为: {linked_list.size}")
    for value in linked_list:
        print(value)
    print("-------------------")
    linked_list.remove_item(1)
    linked_list.remove_item(3)
    print(f"链表长度为: {linked_list.size}")
    for value in linked_list:
        print(value)
    print("-------------------")
